//
// Created by dgy on 2022/11/11.
//
#include "iostream"
using namespace std;
#include "vector"
class Solution{
public:
    /*
     * 递归解决
     * */
    bool verifyPostorder(vector<int> &postorder){
        if (postorder.size()==1||postorder.size()==0)
            return true;
        if (postorder.size()==2){
            if (postorder[1]>postorder[0])
                return true;
            else
                return false;
        }

        return detectPostOrder(postorder,0,postorder.size()-1);
    }
    bool detectPostOrder(vector<int>& postorder,int left,int right){
        if (left>=right)
            return true;
        int root=postorder[right];
        int mid=left;
        while(postorder[mid]<root)
            mid++;
        int temp=mid;
        for (int i = temp; i < right; ++i) {
            if (postorder[i]<root)
                return false;
        }
        return detectPostOrder(postorder,left,mid-1)&&detectPostOrder(postorder,mid,right-1);
    }
    /*
     * 使用栈解决
     * */


};
